package io.github.handyang.algorithms.sort;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class HeapSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        int begin = (arr.length - 1) >> 1;
        for (int i = begin; i >= 0; i--) {
            maxHeap(arr, i, arr.length - 1);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);

            //end 应该为 i-1。i 已经是排序区域
            maxHeap(arr, 0, i - 1);
        }
    }

    private void maxHeap(int[] arr, int start, int end) {
        int left = (start << 1) + 1, right = left + 1;

        if (left > end) return;

        int max = left;
        if (right <= end && less(arr[max], arr[right])) {
            max = right;
        }

        //只需要再次检查被交换的节点
        if (less(arr[start], arr[max])) {
            swap(arr, start, max);
            maxHeap(arr, max, end);
        }

    }
}
